Texture mapping is widely used to improve the visual richness of 3D surfaces in computer generated images. Each 3D surface is put in correspondence with a planar image through a function called a mapping. Such a mapping assigns a pair of coordinates (u,v) referring to a pixel of the planar image to each point of a surface. Thus, for instance, the latitude and longitude can define a trivial mapping of a sphere. This technique was described by E. Catmull in A Subdivision Algorithm for Computer Display of Curved Surfaces, PhD thesis, Dept. of Computer Sciences, University of Utah, December 1974, which is hereby incorporated by reference. This technique was first applied to bicubic patches using a recursive subdivision algorithm. Unfortunately, these methods often produce highly distorted textures in the resulting images, similar to FIG. 10 (which is not prior art, but is only referred to for illustrative purposes).
First attempts to minimize these distortions were described by R. Darwyn Peachey in Solid Texturing of Complex Surfaces, SIGGRAPH 85 Conference Proceedings, volume 19, pages 287-296, ACM, July 1985, and E. Bier and K. Sloan in Two-Part Texture Mapping, IEEE Computer Graphics and Applications, pages 40-53, September 1986, both of which are incorporated herein by reference. These attempts involved separating the process into two steps. The texture pattern is first applied to a simple intermediate surface such as a box or a cylinder for which texture mapping is trivial. Then, this intermediate surface is projected on the target object. The choice of the intermediate surface and its orientation, together with the projection method selected, dramatically affect the results, and great deal of user interaction was therefore required.
Marcel Samek, C. Slean, and H. Weghorst in Texture Mapping and Distortions in Digital Graphics, The Visual Computer, 2(5):313-320, September 1986, which is hereby incorporated by reference, taught that assigning texture coordinates to any surface is equivalent to flattening it. That method consists of unfolding a polygonal surface from a user selected seed. A similar technique was dislosed by C. Bennis, J. M. V'ezien, and G.Igl'esias in Piecewise Surface Flattening for Non-Distorted Texture Mapping, SIGGRAPH 91 Conference Proceedings, volume 25, pages 237-246, ACM, July 1991, which is hereby incorporated by reference. This latter method means a parametric surface may be unfolded by allowing cuts to appear on the mapped texture when the discrepancy of the geodesic curvature goes beyond a given threshold.
Minimizing the distortions induced by texture mapping can be also realized using optimization techniques. In the method described by S. D. Ma and H. Lin in Optimal Texture Mapping, EUROGRAPHICS'88, pages 421-428, September 1988, which is incorporated herein by reference, a mapping of any surface is constructed by starting from a grid of points sampled on the surface. The grid is then iteratively optimized by minimizing a global distortion criterion. V. Krishnamurthy and M. Levoy in Fitting Smooth Surfaces to Dense Polygon Meshes, SIGGRAPH 96 Conference Proceedings, pages 313-324, ACM, August 1996, and incorporated herein by reference, disclosed a similar approach for converting a triangulated mesh into a set of B-Spline surfaces. It is also possible to construct a mapping by assigning (u,v) coordinates to the vertices of the mesh. This naturally leads to the use of harmonic maps, as described by M. Eck, T. DeRose, T. Duchamp, H. Hoppes, M. Lounsbery and W. Stuetzle in Multiresolution Analysis of Arbitrary Meshes, SIGGRAPH 95 Conference Proceedings, pages 173-182, ACM, August 1995, which is hereby incorporated herein by reference. This method consists of minimizing a metric dispersion criterion. Unfortunately, this does not always preserve angles accurately. Another approach disclosed by M. S. Floater in Parametrization and Smooth Approximation of Surface Triangulations, Computer Aided Geometric Design, 14(3):231-250, April 1997, and incorporated herein by reference, generalizes the barycentric mapping method described by W. T. Tutte in Convex Representation of Graphs, Proc. London Math. Soc., volume 10, 1960, also incorporated herein by reference. The (u,v) texture coordinates are found to be the solution of a linear system, where each (u,v) point is a convex combination of its neighbors. M. S. Floater (referenced above) taught a method for choosing the coefficients of these convex combinations to mimic the chord length parametrization for curves. These global methods give good results for most simple surfaces, but suffer from several limitations when applied to more complex surfaces. Further, since the criterion to be minimized is integral to the optimization algorithm, it is often difficult to take into account user defined information. For instance, as most surfaces are not developable, distortions will still remain, and the user may want to specify the distribution of these distortions.
Additionally, it is desirable to have a mapping function that handles "cuts" in the surface, such as for example are found when mapping a geological surface, which may represent a faulted stratigraphic grid. One technique for handling this is described by J. Bloomenthal in Modeling the Mighty Maple, SIGGRAPH 85 Conference Proceedings, volume 19, pages 305-311, ACM, July 1985. Bloomenthal uses several distinct "patches" on the surface and makes the edges of the patches match to provide continuity of a texture over the discontinuity ("cut"). This is a computationally intense method, and it is desirable to provide a simpler method for dealing with discontinuities along a line in the surface.
Prior interactive mapping methods, where the parametrization is partially or completely defined by the user, are described by H. K. Pedersen in Decorating Implicit Surfaces, SIGGRAPH 95 Conference Proceedings, pages 291-300, ACM, 1995, P. Litwinowicz and G. Miller in Efficient Techniques for Interactive Texture Placement, SIGGRAPH 94 Conference Proceedings, pages 119-122, ACM, July 1994, and J. Maillot, H. Yahia, and A. Verroust in Interactive Texture Mapping, SIGGRAPH 93 Conference Proceedings, volume 27, ACM, 1993, all of which are hereby incorporated herein by reference.
Therefore, what is needed in the art is a method for texture mapping onto a surface which reduces distortion of the texture, and which preferably allows for user input to distribute any remaining distortion to preferred regions. Additionally, it is desirable to have a texture mapping method which is capable of handling discontinuities in the surface.